package 左哥算法.ch12滑动窗口与双端队列;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;
import java.util.TreeSet;


public class Ch03一些窗口题目 {

    /**
     * ch01:最长覆盖数
     * 给你一些点num[](有序),这些点分别表示其在数轴上的位置.
     * 给你一个距离N,请问距离N最多能覆盖多少个点
     */
    @Test
    public void test01(){
        compareCh01();
        Integer[] arr={2,4,8,9,12,17};
        int  n=5;
        System.out.println(ch01Fun1(arr, n));
        System.out.println(ch01Fun2(arr, n));
    }

    /**
     * 暴力思路:
     *     1.依次尝试每一个位置作为起点,能覆盖的点数
     *     2.注:找终点可以优化为二分,整体时间复杂度 O(N*logN),但我们主讲滑动窗口,这里就不优化了
     */
    public int ch01Fun1(Integer[] arr,int n){
        Arrays.sort(arr);
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int j=i;
            while (j < arr.length && arr[j] - arr[i] <= n) {
                j++;
            }
            max=Math.max(max,j-i);
        }
        return max;
    }

    /**
     * 滑动思路:
     *      1.依次尝试每一个位置作为起点,能覆盖的点数
     *      2.尝试后的终点为右边界.每次尝试完右边界不回退,左边界移动,再判断终点是否能往右移.
     */
    public int ch01Fun2(Integer[] arr,int n){
        int max=Integer.MIN_VALUE;
        int l=0,r=0;
        while (l < arr.length) {
            while(r< arr.length&&arr[r]-arr[l]<=n){
                r++;
            }
            max = Math.max(max, r - l);
            l++;
        }
        return max;
    }
    public void compareCh01(){
        int count=10000;
        Random r=new Random();
        while (count-- > 0) {
            int n = r.nextInt(100) + 1;
            TreeSet<Integer> set=new TreeSet<>();
            while(set.size()<n){
                set.add(r.nextInt(1000));
            }
            int m=r.nextInt(50)+1;
            Integer[] arr = new Integer[n];
            set.toArray(arr);
            int fun1 = ch01Fun1(arr, m);
            int fun2 = ch01Fun2(arr, m);
            if (fun2!=fun1){
                System.out.println("error");
            }
        }
        System.out.println("ok");
    }
}
